package algorithm.fft;

public class Trigonometry {
	private static final float TWO_PI=(float)Math.PI*2; 
	private float[] cos; 
	private float[] sin;
	private int[] firsts; 
	private int id_quadrant;
	private Complex buff=new Complex(0,0); 
	public Trigonometry(int size, int log2Size){ // size is pow of 2;
		System.out.println("trigonometry creation ...."); 
		firsts=new int[log2Size-1];
		int i,N, K,k,first; 
		int m=2*size-4; 
		cos=new float[m]; 
		sin=new float[m]; 
		for (i=2; i<=log2Size; i++){
			firsts[i-2]=(1<<(i-2))-1;
			N=1<<i; 
			K=N>>2; 
			first=firsts[i-2]; 
			for (k=0; k<K; k++){
				float phi=-k*TWO_PI/N; // can be improved futher;
				cos[k+first]=(float)Math.cos(phi); 
				sin[k+first]=(float)Math.sin(phi); 
			}
		}
	}
	public static Complex testGet(int k, int N){
		float b=-k*TWO_PI/N; 
		Complex c=new Complex(Math.cos(b),Math.sin(b)); 
		return c; 
	}
	public Complex getBase(int kth, int N, int log2N){
		if (N<4){
			return null; 
		}
		int index=firsts[log2N-2]+kth%(N>>2);
		buff.re=cos[index]; 
		buff.im=sin[index]; 
		return buff;  
	}
	public Complex get(int kth, int N, int log2N){
		if (N<4){
			return null; 
		}
		id_quadrant=(kth<<2)/N; // k*4/N;
		int index=firsts[log2N-2]+kth%(N>>2);
		switch(id_quadrant){
		case 0:
			buff.re=cos[index]; 
			buff.im=sin[index]; 
			break; 
		case 1:
			buff.re=sin[index]; 
			buff.im=-cos[index]; 
			break; 
		case 2:
			buff.re=-cos[index]; 
			buff.im=-sin[index]; 
			break; 
		case 3:
			buff.re=-sin[index]; 
			buff.im=cos[index]; 
			break;
		default:
			throw new RuntimeException("=========="); 
		}
		return buff;  
	}	
	public static void main(String[] args){
		testperformance(); 
	}
	public static void testperformance(){
		int order=4; 
		long t0, tt; 
		
		t0=System.currentTimeMillis(); 
		for (order=4; order<20;order++){
			int N=1<<order;  
			int log2N=order; 
			Trigonometry t=new Trigonometry(N,log2N);
			for (int i=0; i<N; i++){
				Complex c1=t.get(i,N, log2N);
			}
		}
		tt=System.currentTimeMillis();
		System.out.println("compute:"+(tt-t0));
		t0=tt; 
		for (order=4; order<20;order++){
			int N=1<<order;  
			//int log2N=order; 
			for (int i=0; i<N; i++){
				Complex c2=testGet(i, N);
			}
		}
		tt=System.currentTimeMillis();
		System.out.println("compute:"+(tt-t0)); 
	}
	public static void testCorrectness(){
		int order=4; 
		for (order=4; order<20;order++){
			int N=1<<order;  
			int log2N=order; 
			Trigonometry t=new Trigonometry(N,log2N);
			for (int i=0; i<N; i++){
				Complex c1=t.get(i,N, log2N);
				Complex c2=t.testGet(i, N);
				Complex diff=c1.minus(c2); 
				double error=Math.abs(diff.re)+Math.abs(diff.im);
				if (error>1.0e-5){
					System.out.println("error:"+error);
					System.out.println(c1+"=="+c2); 
				}
			}
		}
	}
}
